package com.lans.SortAlgorithm;

import java.util.Arrays;

/*
 * @author: lans
 * @date: 2025/1/15
 * @name: 刘宇
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {1,4,12,325,41231231,3,2,432,3131,43245};
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public static void quickSort(int[] arr,int startIndex,int endIndex) {
        //递归停止条件
        if(startIndex>=endIndex) {
            return;
        }
        int pIndex = partition(arr,startIndex,endIndex);
        //对第一轮排序后的基准值左边进行排序
        quickSort(arr,startIndex,pIndex-1);
        //对第一轮排序后的基准值右边进行排序
        quickSort(arr,pIndex+1,endIndex);
    }
    public static int partition(int[] arr,int startIndex,int endIndex){
        int p = arr[startIndex];//基准值
        int l = startIndex;
        int r = endIndex;
        while(l!=r){
            //右边指针 当r在l右侧且该指针指向的元素大于基准元素时左移
            while((l<r)&&(arr[r]>p)){
                r--;
            }
            //左指针 当l还在r右边且该指针指向的元素小于基准元素时右移
            while((l<r)&&(arr[l]<=p)){
                l++;
            }
            //两个循环条件都不满足进行交换 开启新一轮循环
            if(l<r){
                int temp = arr[l];
                arr[l]=arr[r];
                arr[r]=temp;
            }
        }
        //交换基准元素和重合的元素
        arr[startIndex]=arr[l];
        arr[l]=p;
        return l;
    }
}
